package programmercarl.动态规划.C13;

import java.util.Arrays;

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int sum = Arrays.stream(nums).sum();
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp=new int[target+1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >=nums[i] ; j--) {// 0/1背包动态规划的话，必须从后往前遍历，从而保证物品只被放入一次
                //背包容量是sum/2，每个要耗费的容量，是其相应nums[i]的值
                //获得的value是也是其nums[i]的值
                //目标是获得最大的target，看看能不能等于target
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
            if(dp[target]==target)
                return true;
        }
        return dp[target]==target;
    }
}